﻿using System;
using System.Collections.Generic;

namespace h52
{
    public class Solution {
        public class Ufff{
            int[] p;
            public Ufff(int n){
                p = new int[n];
                for (int i = 0; i < p.Length; i++)
                {
                    p[i]=i;
                }
            }
            //成功合并返回主动连接的节点标号，否则返回-1
            public int Union(int x,int y){
                int root1 = Find(x);
                int root2 = Find(y);
                if(root1 == root2){
                    return -1;
                }
                if (root1<root2)
                {
                    p[root2] = root1;
                    return root2;
                }else{
                    p[root1] = root2;
                    return root1;
                }
            }

            private int Find(int x)
            {
                return p[x]==x?x:p[x] = Find(p[x]);
            }
            public void Reset(int x){
                p[x] = x;
            }
        }
        public int mstWeight;
        public IList<IList<int>> FindCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
            //下意识的想法，超时
            //边排序，利用并查集，遍历找到所有最小生成树，在遍历一次边，把边分为三类——关键，伪关键，不关键
            //实际用了题解方法1的解法
            int[][] newEdges = new int[edges.Length][];
            for (int i = 0; i < edges.Length; i++)
            {
                newEdges[i] = new int[4];
                newEdges[i][0] = edges[i][0];
                newEdges[i][1] = edges[i][1];
                newEdges[i][2] = edges[i][2];
                newEdges[i][3] = i;
            }
            Array.Sort(newEdges,(e1,e2)=>e1[2].CompareTo(e2[2]));
            Ufff uf = new Ufff(n);
            int edgeCountStillNeeded = n-1;
            mstWeight = 0;
            for (int i = 0; i < newEdges.Length; i++)
            {
                if (-1!=uf.Union(newEdges[i][0],newEdges[i][1]))
                {
                    mstWeight+=newEdges[i][2];
                    edgeCountStillNeeded--;
                }
                if (edgeCountStillNeeded==0)
                {
                    break;
                }
            }
            List<IList<int>> result = new List<IList<int>>();
            result.Add(new List<int>());//关键
            result.Add(new List<int>());//伪关键
            HashSet<int> hs = new HashSet<int>();
            //找关键边
            for (int i = 0; i < newEdges.Length; i++)
            {
                int thisWeight = 0;
                int thisNeedCount = n-1;
                uf = new Ufff(n);
                for (int j = 0; j < newEdges.Length; j++)
                {
                    if (i==j)
                    {
                        continue;
                    }
                    if (-1!=uf.Union(newEdges[j][0],newEdges[j][1]))
                    {
                        thisWeight+=newEdges[j][2];
                        thisNeedCount--;
                    }
                    if (thisNeedCount==0)
                    {
                        break;
                    }
                }
                if (thisNeedCount!=0 || thisWeight!=mstWeight)
                {
                    result[0].Add(newEdges[i][3]);
                    hs.Add(newEdges[i][3]);
                }
            }
            //找伪关键边
            for (int i = 0; i < newEdges.Length; i++)
            {
                if (hs.Contains(newEdges[i][3]))
                {
                    continue;
                }
                int thisWeight = newEdges[i][2];
                int thisNeedCount = n-2;
                uf = new Ufff(n);
                uf.Union(newEdges[i][0],newEdges[i][1]);
                for (int j = 0; j < newEdges.Length; j++)
                {
                    if (i==j)
                    {
                        continue;
                    }
                    if (-1!=uf.Union(newEdges[j][0],newEdges[j][1]))
                    {
                        thisWeight+=newEdges[j][2];
                        thisNeedCount--;
                    }
                    if (thisNeedCount==0)
                    {
                        break;
                    }
                }
                if (thisWeight==mstWeight)
                {
                    result[1].Add(newEdges[i][3]);
                }
            }
            return result;
        }
}

}